# _*_coding:UTF-8 _*_
import random


# 冒泡排序时间复杂度O(n**2)
def bubble_sort(li):
    for i in range(len(li) - 1):
        for j in range(len(li) - i - 1):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]


li = [random.randint(0, 1000) for i in range(1000)]
# li = [634, 530, 200, 146, 882, 370, 670, 222, 310, 759, 90, 258, 575, 769, 936, 265, 440, 37, 699, 349, 382, 269, 808, 595, 316, 647, 159, 719, 69, 8, 307, 627, 167, 51, 735, 65, 722, 418, 319, 936, 762, 981, 946, 489, 890, 900, 195, 155, 230, 850, 399, 296, 242, 576, 19, 580, 915, 336, 168, 736, 946, 819, 911, 386, 982, 316, 376, 820, 508, 843, 133, 658, 71, 986, 202, 130, 215, 104, 549, 91, 841, 696, 697, 728, 21, 355, 387, 506, 977, 27, 470, 169, 216, 469, 190, 686, 762, 892, 303, 225, 203, 52, 580, 219, 571, 786, 36, 72, 103, 359, 94, 532, 666, 621, 697, 978, 695, 289, 534, 281, 897, 40, 402, 307, 232, 481, 632, 890, 446, 837, 282, 898, 517, 901, 72, 612, 767, 903, 565, 786, 387, 160, 188, 892, 690, 520, 1000, 779, 476, 576, 711, 488, 127, 337, 397, 453, 562, 479, 415, 855, 126, 63, 926, 880, 539, 405, 753, 294, 628, 427, 4, 573, 685, 143, 762, 732, 891, 827, 601, 697, 808, 122, 331, 453, 812, 981, 228, 254, 617, 662, 799, 749, 460, 435, 8, 101, 720, 104, 439, 35, 570, 800, 118, 553, 717, 46, 768, 855, 347, 401, 217, 453, 688, 208, 177, 569, 793, 584, 600, 734, 580, 339, 936, 382, 568, 792, 829, 237, 380, 566, 519, 190, 299, 41, 890, 737, 337, 275, 142, 726, 190, 206, 276, 460, 938, 466, 39, 861, 684, 239, 564, 659, 137, 446, 407, 441, 660, 214, 165, 413, 474, 797, 269, 43, 921, 890, 615, 956, 69, 383, 573, 29, 110, 310, 258, 398, 482, 335, 997, 351, 749, 487, 674, 608, 836, 454, 311, 760, 230, 297, 741, 230, 256, 237, 861, 884, 864, 211, 31, 266, 970, 765, 377, 816, 180, 411, 124, 394, 403, 447, 211, 114, 603, 269, 245, 226, 182, 390, 946, 749, 782, 686, 324, 825, 360, 663, 416, 954, 602, 143, 852, 685, 390, 528, 575, 851, 999, 296, 146, 600, 898, 107, 13, 86, 189, 811, 589, 92, 924, 422, 490, 954, 833, 421, 93, 518, 338, 863, 446, 171, 643, 409, 170, 122, 265, 490, 721, 229, 65, 820, 51, 581, 869, 459, 544, 54, 537, 238, 193, 315, 868, 109, 484, 179, 124, 618, 152, 140, 101, 200, 630, 226, 873, 461, 958, 307, 625, 377, 578, 103, 492, 376, 86, 757, 528, 85, 968, 897, 262, 462, 773, 347, 987, 894, 116, 675, 503, 764, 892, 226, 332, 214, 162, 306, 66, 861, 778, 953, 205, 682, 63, 514, 704, 173, 433, 605, 431, 304, 142, 21, 974, 240, 617, 480, 946, 565, 305, 668, 344, 296, 448, 319, 522, 977, 262, 95, 725, 351, 948, 978, 152, 839, 419, 964, 53, 670, 593, 937, 255, 496, 134, 845, 946, 503, 853, 625, 173, 7, 19, 453, 722, 376, 847, 916, 884, 834, 180, 829, 349, 295, 935, 837, 954, 637, 582, 35, 314, 251, 444, 643, 235, 676, 467, 433, 964, 721, 925, 373, 470, 615, 522, 477, 557, 412, 949, 298, 398, 2, 735, 211, 505, 367, 951, 962, 998, 477, 532, 515, 793, 161, 931, 903, 351, 386, 12, 853, 842, 637, 457, 68, 180, 326, 769, 74, 901, 661, 107, 972, 241, 888, 29, 6, 506, 55, 950, 140, 670, 348, 751, 329, 543, 826, 147, 66, 325, 952, 123, 765, 434, 171, 83, 611, 842, 862, 502, 110, 533, 44, 78, 645, 482, 934, 768, 512, 935, 45, 530, 74, 391, 946, 20, 152, 425, 966, 832, 106, 835, 780, 376, 565, 526, 503, 891, 555, 837, 713, 731, 881, 654, 22, 40, 552, 841, 334, 456, 76, 573, 329, 474, 889, 504, 264, 816, 185, 871, 381, 599, 745, 134, 481, 580, 772, 545, 476, 497, 752, 412, 197, 842, 477, 858, 43, 80, 368, 819, 848, 244, 807, 617, 991, 99, 616, 641, 629, 165, 52, 34, 478, 67, 11, 426, 532, 330, 495, 441, 970, 203, 58, 711, 698, 32, 975, 972, 741, 539, 904, 833, 365, 273, 455, 927, 562, 467, 409, 4, 154, 755, 53, 465, 703, 62, 417, 662, 183, 155, 297, 789, 262, 313, 984, 809, 128, 841, 475, 362, 903, 741, 94, 595, 546, 684, 76, 687, 988, 459, 409, 757, 122, 687, 66, 223, 251, 327, 432, 205, 740, 849, 530, 420, 869, 12, 327, 954, 780, 762, 572, 834, 461, 244, 344, 398, 422, 780, 119, 149, 96, 507, 742, 857, 499, 537, 714, 548, 566, 635, 717, 535, 172, 890, 847, 528, 966, 790, 140, 234, 66, 630, 482, 255, 974, 129, 714, 79, 739, 953, 428, 151, 483, 109, 311, 241, 919, 248, 932, 473, 609, 71, 184, 198, 400, 784, 953, 146, 37, 284, 952, 452, 421, 841, 167, 878, 726, 402, 679, 96, 54, 232, 330, 377, 407, 426, 827, 426, 546, 964, 141, 120, 196, 404, 417, 390, 0, 937, 618, 894, 302, 431, 836, 812, 243, 647, 73, 904, 547, 701, 319, 935, 724, 544, 255, 46, 627, 948, 712, 63, 36, 809, 678, 895, 422, 743, 459, 812, 278, 808, 798, 661, 590, 467, 318, 883, 890, 561, 936, 542, 941, 63, 809, 920, 539, 732, 355, 955, 85, 907, 986, 833, 939, 172, 837, 114, 190, 685, 439, 961, 690, 720, 366, 8, 287, 309, 644, 583, 914, 260, 434, 922, 361, 94, 753, 934, 768, 928, 819, 489, 442, 993, 261, 353, 283, 144, 411, 391, 764, 632, 183, 762, 848, 752, 854, 751, 888, 24, 212, 739, 688, 216, 521, 879, 546, 792, 153, 558, 660, 84, 678, 542, 791, 678, 911, 678, 304, 489, 838, 956, 576, 554, 526, 121, 780, 957, 328, 494, 100, 183, 498, 812, 867, 545, 906, 75, 656, 250, 0, 485, 12, 494, 401, 624, 494, 536, 179, 693, 964, 385, 777, 893, 788, 159, 107, 554, 390, 374, 703, 860, 565, 700, 691, 988, 993, 761, 565, 697, 901, 959, 680, 90, 464, 620, 97]
# print(li)
bubble_sort(li)
print(li)
